'''
给定一个列表和一个整数,设计算法找到两个数的下标,使得两个数之和为给定的整数.保证肯定仅有一个结果
例如,列表[1,2,5,4]与目标整数3,1+2=3,结果为(0,1)
'''
# def func(li,target):
#     for i in li:
#         for j in li[li.index(i)+1:len(li)+1]:
#             if i + j == target:
#                 return li.index(i),li.index(j)
#
# li = [1,2,4,5]
# print(func(li,3))

class Solution:
    # 二分查找实现：在有序列表的指定区间查找目标值
    def binary_search(self, li, left, right, val):
        # 当搜索区间有效时循环（左边界 <= 右边界）
        while left <= right:
            # 计算中间索引位置
            mid = (left + right) // 2
            # 如果中间值等于目标值，返回索引
            if li[mid][0] == val:  # 注意：实际比较列表元素的值（子数组第一项）
                return mid
            # 中间值比目标值大，缩小右边界
            if li[mid][0] > val:
                right = mid - 1
            # 中间值比目标值小，缩小左边界
            else:
                left = mid + 1
        # 未找到目标值时返回None
        else:
            return None

    # 两数之和解法：找出数组中相加等于目标的两个数的索引
    def twoSum(self, nums, target):
        # 创建二维数组：[[数值, 原索引], ...]
        new_nums = [[num, i] for i, num in enumerate(nums)]
        # 按数值从小到大排序（关键步骤）
        new_nums.sort(key=lambda x: x[0])

        # 遍历排序后的数组
        for i in range(len(new_nums)):
            # 当前元素值a（a = new_nums[i][0]）
            a = new_nums[i][0]
            # 计算所需配对值b（target - a）
            b = target - a  # 提取数值部分

            # 二分查找策略选择
            if b >= a:
                # 当b >= a时，在右侧区间查找（避免重复配对）
                j = self.binary_search(new_nums, i + 1, len(new_nums) - 1, b)
            else:
                # 当b < a时，在左侧区间查找
                j = self.binary_search(new_nums, 0, i - 1, b)

            # 如果找到配对元素
            if j is not None:  # 注意：j为0时是有效索引
                # 退出循环（已找到解）
                break

        # 返回排序后的原索引对（保持小索引在前）
        return sorted(new_nums[i][1], new_nums[j][1])  # 提取原始索引位置